import java.util.List;
import java.util.ArrayList;

public class Move {
    static final byte MOVE_NORMAL = 0;
    static final byte MOVE_PUSH = 1;
    static final byte MOVE_NORTH = (1 << 1);
    static final byte MOVE_SOUTH = (1 << 2);
    static final byte MOVE_WEST = (1 << 3);
    static final byte MOVE_EAST = (1 << 4);

	boolean isNormal(){ return (moveType^MOVE_NORMAL)==0 ? true : false; }
	boolean isPush(){ return (moveType&MOVE_PUSH)!=0 ? true : false; }
	boolean isNorth(){ return (moveType&MOVE_NORTH)!=0 ? true : false; }
	boolean isSouth(){ return (moveType&MOVE_SOUTH)!=0 ? true : false; }
	boolean isWest(){ return (moveType&MOVE_WEST)!=0 ? true : false; }
	boolean isEast(){ return (moveType&MOVE_EAST)!=0 ? true : false; }

	static boolean isNormal(byte b){ return (b^MOVE_NORMAL)==0 ? true : false; }
	static boolean isPush(byte b){ return (b&MOVE_PUSH)!=0 ? true : false; }
	static boolean isNorth(byte b){ return (b&MOVE_NORTH)!=0 ? true : false; }
	static boolean isSouth(byte b){ return (b&MOVE_SOUTH)!=0 ? true : false; }
	static boolean isWest(byte b){ return (b&MOVE_WEST)!=0 ? true : false; }
	static boolean isEast(byte b){ return (b&MOVE_EAST)!=0 ? true : false; }

    private byte moveType;

    public Move(byte t) {
        moveType = t;
    }

    static List<Move> findAllPossibleMoves(Board b, GameState gs, Move lastMove) {
        ArrayList<Move> moves = new ArrayList<Move>();
		int[] rc = gs.getPlayerPos();

		moveMoveInDirection(moves, b, gs, lastMove, rc, MOVE_NORTH);
		moveMoveInDirection(moves, b, gs, lastMove, rc, MOVE_SOUTH);
		moveMoveInDirection(moves, b, gs, lastMove, rc, MOVE_EAST);
		moveMoveInDirection(moves, b, gs, lastMove, rc, MOVE_WEST);

//		// fly() grejs:
//		boolean[][][] p = genBool(b, gs);
//		ArrayList<ArrayList<Move>> listOfLists = new ArrayList<ArrayList<Move>>();
//		ArrayList<FlyNode> queue = new ArrayList<FlyNode>();
//		FlyNode f = new FlyNode(new ArrayList<Move>(), rc);
//		queue.add(f);
//		fly(listOfLists, queue, p, rc, b, gs, 10);
//		// Jag vet inte om fly funkar, men här ska vi iaf returnera listOfList till "den stora" sökningen
//		// fly() grejs slut.
		
		
        return moves;
    }

	// TODO lastMove
	static List<List<Move>> findAllPossibleMoves(Board b, GameState gs, int depth) {
		int[] rc = gs.getPlayerPos();
		boolean[][][] p = genBool(b, gs);
		List<List<Move>> listOfLists = new ArrayList<List<Move>>();
		ArrayList<FlyNode> queue = new ArrayList<FlyNode>();
		FlyNode f = new FlyNode(new ArrayList<Move>(), rc);
		queue.add(f);
		fly(listOfLists, queue, p, rc, b, gs, depth);
//		pr(b, p, 0);
//		pr(b, p, 1);
		// Jag vet inte om fly funkar, men här ska vi iaf returnera listOfList till "den stora" sökningen

//		U.pr("antal: "+listOfLists.size());
        return listOfLists;
    }

	// rc is the orginal player pos.
	private static void fly(List<List<Move>> listOfLists, ArrayList<FlyNode> queue, boolean[][][] p, int[] rc, Board b, GameState gs, int depth){
		if(queue.size()<=0){
			return;
		}

		FlyNode f = queue.get(0);
		queue.remove(0);
		
		if(f.moves == null || depth > f.moves.size()){
			for(int dir = 0; dir < 4; dir++){
	//			U.pr("\ndir: "+dir);
	//			U.pr("III; x: "+f.pos[0]+"	y:"+f.pos[1]);
	//			U.pr("INN; x: "+nextPos(dir, f.pos)[0]+"	y:"+nextPos(dir, f.pos)[1]);
				FlyNode e = expand(f, nextPos(dir, f.pos), dir, p, b, gs);
	//			U.pr("dir: "+dir);
	//			U.pr("EEE; x: "+f.pos[0]+"	y:"+f.pos[1]);
	//			U.pr("ENN; x: "+nextPos(dir, f.pos)[0]+"	y:"+nextPos(dir, f.pos)[1]);
				if(e != null){
					if(e.isPush){
	//					U.pr("dir: "+dir+"	Push");
						listOfLists.add(e.moves);
//						U.pr("size: "+e.moves.size());
					}else{// is a move
//						U.pr("dir: "+dir+"	Move");
						queue.add(e);
					}
				}else{

				}
			}
		}
		
		fly(listOfLists, queue, p, rc, b, gs, depth);// iterate
	}

	// return null if the node is not a push nore a move.
	static FlyNode expand(FlyNode f, int[] rc, int dir, boolean[][][] p, Board b, GameState gs){
//		Move m = flyIsMove(rc, dir, p);
		boolean r = false;
//		if(dir==1 && rc[1]==4 && rc[0]==2)
//			r = true;
		if(r)
		U.pr("x: "+rc[0]+"	y: "+rc[1]+"	dir: "+dir);
//		Move m = isPush(dir, rc, b, gs);
		Move m = isPush(dir, f.pos, b, gs);// OBS f.pos för att kolla om det tidigare draget + denna riktning gav upphov till en push (rc står alltså på ett block)
//		Move m = isPush(dir, p, rc, b, gs);
//		Move m = isPush(dir, p, f.pos, b, gs);// OBS f.pos för att kolla om det tidigare draget + denna riktning gav upphov till en push (rc står alltså på ett block)
		if(m!=null){
			FlyNode me = new FlyNode(f.moves, true);
			me.moves.add(m);
			me.pos = new int[]{rc[0], rc[1]};
			if(r)
			U.pr("is push");
			return me;
		}
		m = flyIsMove(rc, dir, p);
		if(m!=null){
			FlyNode me = new FlyNode(f.moves, false);
			me.moves.add(m);
			me.pos = new int[]{rc[0], rc[1]};
			if(r)
			U.pr("is move");
			return me;
		}

		return null;
	}

	// Som A fast för många saker sammtidigt, "målen" är lagrade som TRUE i "brädet" toThisPos[][] som enbart ska innehålla TRUE för mål, och FALSE för allt annat, "målen" kan vara goals eller någonting annat av inträsse.
	static void findPathTo(int[] solutions, ArrayList<DistNode> queue, boolean[][] p, boolean[][] toThisPos, Board b, GameState gs, int depth, int posesLeft, int[][] posOfEndPoints){
		if(queue.isEmpty()){
			return;
		}
		DistNode d = queue.get(0);
		queue.remove(0);
		if(depth > d.moves){
			if(isAtThis(d.pos, toThisPos)){
				toThisPos[d.pos[0]][d.pos[1]] = false;
				p[d.pos[0]][d.pos[1]] = false;
				solutions[posOfEndPoints[d.pos[0]][d.pos[1]]] = d.moves;
				posesLeft--;
			}
			if(posesLeft<=0){
				return;
			}
			d.moves++;
			for(int dir = 0; dir < 4; dir++){
				int[] c = nextPos(dir, d.pos);
				if(isWalkable(p, c[0], c[1])){
					p[c[0]][c[1]] = false;
					queue.add(new DistNode(d.moves, c));
				}
			}
		}
		findPathTo(solutions, queue, p, toThisPos, b, gs, depth, posesLeft, posOfEndPoints);// iterate
	}

	// A*
//	static int findPathTo1Pos(ArrayList<DistNodeAStar> queue, boolean[][] p, int[] toThisPos, Board b, GameState gs, int depth){
//		if(queue.isEmpty()){
//			return -1;
//		}
//		b.nodes++;
////		DistNodeAStar d = queue.get(lowest);
////		queue.remove(lowest);
//		DistNodeAStar d = queue.get(0);
//		queue.remove(0);
//		if(depth > d.moves){
//			if(d.pos[0] == toThisPos[0] && d.pos[1] == toThisPos[1]){
////				p[d.pos[0]][d.pos[1]] = false;
//				return d.moves;
//			}
//			d.moves++;
//			for(int dir = 0; dir < 4; dir++){
//				int[] c = nextPos(dir, d.pos);
//				if(isWalkable(p, c[0], c[1])){
//					p[c[0]][c[1]] = false;
////					queue.add(new DistNodeAStar(d.moves, c, d.H+1, d.H+1+calcG(c, toThisPos)));
//					addToQueue(queue, d.moves, c, d.H+1, d.H+1+calcG(c, toThisPos));
//				}
//			}
//		}
//		return findPathTo1Pos(queue, p, toThisPos, b, gs, depth);// iterate
//	}
//
//	static void addToQueue(ArrayList<DistNodeAStar> queue, int moves, int[] pos, int H, int F){
//		for(int i = 0; i < queue.size(); i++){
//			if(queue.get(i).F >= F){
//				queue.add(i, new DistNodeAStar(moves, pos, H, F));
//				return;
//			}
//		}
//	}

	// TEST
//	static int findPathTo1Pos(ArrayList<DistNodeAStar> queue, int[] toThisPos, Board b, GameState gs, int depth){
//		if(queue.isEmpty()){
//			return -1;
//		}
//		b.nodes++;
////		DistNodeAStar d = queue.get(lowest);
////		queue.remove(lowest);
//		DistNodeAStar d = queue.get(0);
//		queue.remove(0);
//		if(depth > d.moves){
//			if(d.pos[0] == toThisPos[0] && d.pos[1] == toThisPos[1]){
////				p[d.pos[0]][d.pos[1]] = false;
//				return d.moves;
//			}
//			d.moves++;
//			for(int dir = 0; dir < 4; dir++){
//				int[] c = nextPos(dir, d.pos);
//				addToQueue(queue, d.moves, c, d.H+1, 2*(d.H+1+calcG(c, toThisPos)));
//			}
//		}
//		return findPathTo1Pos(queue, toThisPos, b, gs, depth);// iterate
//	}
//
//	static void addToQueue(ArrayList<DistNodeAStar> queue, int moves, int[] pos, int H, int F){
//		for(int i = 0; i < queue.size(); i++){
//			if(queue.get(i).F > F){
//				queue.add(i, new DistNodeAStar(moves, pos, H, F));
//				return;
//			}else if(queue.get(i).F == F){
////				queue.add(i, new DistNodeAStar(moves, pos, H, F));
//				return;
//			}
//		}
//	}

//	 A*
	static int findPathTo1Pos(ArrayList<DistNodeAStar> queue, boolean[][] p, int[] toThisPos, Board b, GameState gs, int depth){
		if(queue.isEmpty()){
			return -1;
		}
		b.nodes++;
		int lowest = lowestF(queue);
		DistNodeAStar d = queue.get(lowest);
		queue.remove(lowest);
		if(depth > d.moves){
			if(d.pos[0] == toThisPos[0] && d.pos[1] == toThisPos[1]){
//				p[d.pos[0]][d.pos[1]] = false;
				return d.moves;
			}
			d.moves++;
			for(int dir = 0; dir < 4; dir++){
				int[] c = nextPos(dir, d.pos);
				if(isWalkable(p, c[0], c[1])){
					p[c[0]][c[1]] = false;
					queue.add(new DistNodeAStar(d.moves, c, d.H+1, d.H+1+calcG(c, toThisPos)));
				}
			}
		}
		return findPathTo1Pos(queue, p, toThisPos, b, gs, depth);// iterate
	}

//	// TEST
//	static int findPathTo1Pos(ArrayList<DistNodeAStar> queue, int[] toThisPos, Board b, GameState gs, int depth){
//		if(queue.isEmpty()){
//			return -1;
//		}
//		b.nodes++;
//		int lowest = lowestF(queue);
//		DistNodeAStar d = queue.get(lowest);
//		queue.remove(lowest);
//		if(depth > d.moves){
//			if(d.pos[0] == toThisPos[0] && d.pos[1] == toThisPos[1]){
////				p[d.pos[0]][d.pos[1]] = false;
//				return d.moves;
//			}
//			d.moves++;
//			pr("moves: "+d.moves);
//			for(int dir = 0; dir < 4; dir++){
//				int[] c = nextPos(dir, d.pos);
//					queue.add(new DistNodeAStar(d.moves, c, d.H+1, d.H+1+calcG(c, toThisPos)));
//			}
//		}
//		return findPathTo1Pos(queue, toThisPos, b, gs, depth);// iterate
//	}

	
	static DistNodeAStar findPathNodeTo1Pos(ArrayList<DistNodeAStar> queue, boolean[][] p, int[] toThisPos, Board b, GameState gs, int depth){
		if(queue.isEmpty()){
			return null;
		}
		b.nodes++;
		int lowest = lowestF(queue);
		DistNodeAStar d = queue.get(lowest);
		queue.remove(lowest);
		if(depth > d.moves){
			if(d.pos[0] == toThisPos[0] && d.pos[1] == toThisPos[1]){
//				p[d.pos[0]][d.pos[1]] = false;
				return d;
			}
			d.moves++;
			for(int dir = 0; dir < 4; dir++){
				int[] c = nextPos(dir, d.pos);
				if(isWalkable(p, c[0], c[1])){
					p[c[0]][c[1]] = false;
					queue.add(new DistNodeAStar(d.moves, c, d.H+1, d.H+1+calcG(c, toThisPos)));
				}
			}
		}
		return findPathNodeTo1Pos(queue, p, toThisPos, b, gs, depth);// iterate
	}

	static int lowestF(ArrayList<DistNodeAStar> queue){
		int bestI=0;
		int best=queue.get(0).F;
		for(int i = 1; i < queue.size(); i++){
//			if(best==null || d.G+d.H < best.G+best.H){
			int F = queue.get(i).F;
			if(F < best){
				best=F;
				bestI=i;
			}
		}
		return bestI;
	}

	static int calcG(int[] from, int[] to){
		return Math.abs(from[0]-to[0]) + Math.abs(from[1]-to[1]);
	}


	// A
//	static int findPathTo1Pos(ArrayList<DistNode> queue, boolean[][] p, int[] toThisPos, Board b, GameState gs, int depth){
//		if(queue.isEmpty()){
//			return -1;
//		}
//		DistNode d = queue.get(0);
//		queue.remove(0);
//		if(depth > d.moves){
//			if(d.pos[0] == toThisPos[0] && d.pos[1] == toThisPos[1]){
////				p[d.pos[0]][d.pos[1]] = false;
//				return d.moves;
//			}
//			d.moves++;
//			for(int dir = 0; dir < 4; dir++){
//				int[] c = nextPos(dir, d.pos);
//				if(isWalkable(p, c[0], c[1])){
//					p[c[0]][c[1]] = false;
//					queue.add(new DistNode(d.moves, c));
//				}
//			}
//		}
//		return findPathTo1Pos(queue, p, toThisPos, b, gs, depth);// iterate
//	}

	// rc is the players pos;
	static boolean  isAtThis(int[] rc, boolean[][] goals){
		if(rc[0]>=0 && rc[1]>=0 && rc[0]<goals.length && rc[1]<goals[0].length){
			return goals[rc[0]][rc[1]];
		}
		return false;
	}

	// rc is the players pos;
	static boolean  isGoal(int[] rc, boolean[][] goals){
		if(rc[0]>=0 && rc[1]>=0 && rc[0]<goals.length && rc[1]<goals[0].length){
			return goals[rc[0]][rc[1]];
		}
		return false;
	}
	// rc is the players pos;
	static boolean  runIsMove(int[] rc, boolean[][] p){
		if(isWalkable(p, rc[0], rc[1])){
//			U.pr("W; x:"+rc[0]+"	y:"+rc[1]);
			p[rc[0]][rc[1]] = false;// nu kan man inte längre gå på rutan (prg. den är redan sökt).
			return true;
		}
		return false;
	}

	// rc is the players pos;
	static Move flyIsMove(int[] rc, int dir, boolean[][][] p){
		if(isWalkable(p, rc[0], rc[1])){
//			U.pr("W; x:"+rc[0]+"	y:"+rc[1]);
			p[rc[0]][rc[1]][0] = false;// nu kan man inte längre gå på rutan (prg. den är redan sökt).
//			return new FlyNode(getMove(dir, false));
			return getMove(dir, false);
		}
		return null;
	}


	// returnerar ett Move om det går att pusha, null annars.
	// gs måste inte intehålla playerns nya position, men alla block och deras positioner.
	private static Move isPush(int direction, int[] playerNewPos, Board b, GameState gs){
		Move dir = getMove(direction, true);
		int[] pDest = b.posInDirection(dir, playerNewPos);
		byte gsDir = gs.At(pDest);
		byte dirB = b.At(pDest);
		if(!Board.isInvalid(dirB) && !Board.isWall(dirB)){
//			U.pr("1");
			if(GameState.isBlock(gsDir)){
//				U.pr("2");
				int[] posAfterBlock = b.posInDirection(dir, pDest);
				byte afterBlock = b.At(posAfterBlock);
				byte gsAfterBlock = gs.At(posAfterBlock);
				// Om rutan som blocket kommer på är ett hörn, så vill vi inte putta in den dit. men om hörnet är ett tomt mål, då kan vi putta den dit.
				if(!Board.isInvalid(afterBlock) && ((!Board.isWall(afterBlock) && !GameState.isBlock(gsAfterBlock))) && (!Board.isCorner(afterBlock) || Board.isGoal(afterBlock))){
//					byte t = getMoveDirection(dirM, false);
//					moves.add(new Move(t));
//					U.pr("3");
					return dir;
				}
			}
		}
		return null;
	}

	//TODO optimera
	private static Move isPush(int direction, boolean[][][] p, int[] playerNewPos, Board b, GameState gs){
		Move dir = getMove(direction, true);
		int[] pDest = b.posInDirection(dir, playerNewPos);
		byte gsDir = gs.At(pDest);
//		U.pr("pDest; x:"+pDest[0]+"	y:"+pDest[1]);
		boolean isDestNotWallNoreInvalid = p[pDest[0]][pDest[1]][0];
		boolean isDestBlock = p[pDest[0]][pDest[1]][1];

		if(isDestNotWallNoreInvalid){
//		byte dirB = b.At(pDest);
//		if(!Board.isInvalid(dirB) && !Board.isWall(dirB)){// kan användas istället för isNotWallNoreInvalid
//			if(GameState.isBlock(gsDir)){
			if(isDestBlock){
				int[] posAfterBlock = b.posInDirection(dir, pDest);
				byte afterBlock = b.At(posAfterBlock);
				byte gsAfterBlock = gs.At(posAfterBlock);
				// Om rutan som blocket kommer på är ett hörn, så vill vi inte putta in den dit. men om hörnet är ett tomt mål, då kan vi putta den dit.
				if(!Board.isInvalid(afterBlock) && ((!Board.isWall(afterBlock) && !GameState.isBlock(gsAfterBlock))) && (!Board.isCorner(afterBlock) || Board.isGoal(afterBlock))){
//					byte t = getMoveDirection(dirM, false);
//					moves.add(new Move(t));
					p[pDest[0]][pDest[1]][0]=false;
					return dir;
				}
			}
		}
		return null;
	}
	

	static void pr(Board b, boolean[][][] p, int i){
		U.pr("\n"+i);
		for(int r = 0; r < b.mCellRows; r++){
			String s = "";
			for(int c = 0; c < b.mCellCols; c++){
				s += p[r][c][i]==true ? "1" : "0";
			}
			U.pr(s);
		}
		U.pr("");
	}

	// rc är playerns pos i förra "stora sökningen" och lastMove är riktningen...
	static boolean[][][] genBool(Board b, GameState gs){
		
		boolean[][][] p = new boolean[b.mCellRows][b.mCellCols][2];
		for(int r = 0; r < b.mCellRows; r++){
			for(int c = 0; c < b.mCellCols; c++){
				if(!b.isWall(r, c) && !b.isInvalid(r, c)){
					if(!gs.isPlayer(gs.At(new int[]{r,c}))){
						if(!gs.isBlock(gs.At(new int[]{r,c}))){
							p[r][c][0] = true;
							p[r][c][1] = false;
						}else{
							p[r][c][0] = false;
							p[r][c][1] = true;
						}
					}else{
						p[r][c][0] = false;// OBS
						p[r][c][1] = false;
					}
				}else{
					p[r][c][0] = false;
					p[r][c][1] = false;
				}
			}
		}


//		for(int r = 0; r < b.mCellRows; r++){
//			for(int c = 0; c < b.mCellCols; c++){
//				if(!b.isWall(r, c) && !b.isInvalid(r, c)){
//					if(gs.isBlock(gs.At(new int[]{r,c}))){
//						if(genTarget(p, r-1, c))
//							p[r-1][c][1]=true;
//						if(genTarget(p, r+1, c))
//							p[r+1][c][1]=true;
//						if(genTarget(p, r, c-1))
//							p[r][c-1][1]=true;
//						if(genTarget(p, r, c+1))
//							p[r][c+1][1]=true;
//					}
//				}
//			}
//		}
		return p;
	}

	// a target is a valid cell next to a block
	static boolean isWalkable(boolean[][][] p, int r, int c){
		if(r>=0 && c>=0 && r<p.length && c<p[0].length){
			return p[r][c][0];
		}
		return false;
	}
	// a target is a valid cell next to a block
	static boolean isWalkable(boolean[][] p, int r, int c){
		if(r>=0 && c>=0 && r<p.length && c<p[0].length){
			return p[r][c];
		}
		return false;
	}

	// a target is a valid cell next to a block
	static boolean genTarget(boolean[][][] p, int r, int c){
		if(r>=0 && c>=0 && r<p.length && c<p[0].length){
			if(p[r][c][0]!=false){
				return true;
			}
		}
		return false;
	}

	static void moveMoveInDirection(ArrayList<Move> moves, Board b, GameState gs, Move lastMove, int[] rc, byte direction){
		Move dirM = new Move(direction);
		// rc playerPos()
		int[] pDest = b.posInDirection(dirM, rc);
		byte dir = b.At(pDest);
		byte gsDir = gs.At(pDest);
		if(!Board.isInvalid(dir) && !Board.isWall(dir)){
			if(GameState.isBlock(gsDir)){
				int[] posAfterBlock = b.posInDirection(dirM, pDest);
				byte afterBlock = b.At(posAfterBlock);
				byte gsAfterBlock = gs.At(posAfterBlock);
				int[] posAfterBlock2 = b.posInDirection(dirM, posAfterBlock);
				byte afterBlock2 = b.At(posAfterBlock2);
				byte gsAfterBlock2 = gs.At(posAfterBlock2);
				// Om rutan som blocket kommer på är ett hörn, så vill vi inte putta in den dit. men om hörnet är ett tomt mål, då kan vi putta den dit.
//				if(!Board.isInvalid(afterBlock) && ((!Board.isCorner(afterBlock) && Board.isEmpty(afterBlock)) || (Board.isGoal(afterBlock) && !GameState.isBlock(gsAfterBlock)))){
//				if(!Board.isInvalid(afterBlock) && ((!Board.isCorner(afterBlock)) || (Board.isGoal(afterBlock) && !GameState.isBlock(gsAfterBlock)))){
//				if(!Board.isInvalid(afterBlock) && ((!Board.isWall(afterBlock) && !GameState.isBlock(gsAfterBlock))) && (!Board.isCorner(afterBlock) || Board.isGoal(afterBlock))){
				if(!Board.isInvalid(afterBlock) && ((!Board.isWall(afterBlock) && !GameState.isBlock(gsAfterBlock))) && (!Board.isCorner(afterBlock) || Board.isGoal(afterBlock))){
//					if(GameState.isBlock(gsAfterBlock2) && ((Board.isWallX(afterBlock2) && Board.isWallX(afterBlock)) || (Board.isWallY(afterBlock2) && Board.isWallY(afterBlock)))){
//						U.pr("hej");
////						return; // om två block nuddar varandra, och båda är WallX eller båda är WallY så är det dead lock.
//					}
					byte t = getMoveDirection(dirM, false);
					moves.add(new Move(t));
				}
			}else if(lastMove==null || (lastMove.isPush() || (!isInversDirection(lastMove, dirM)))){
				byte t = getMoveDirection(dirM, true);
				moves.add(new Move(t));
			}
		}
	}

	

	static boolean isInversDirection(Move m1, Move m2){
		if(m1.isNorth() && m2.isSouth())
			return true;
		if(m1.isSouth() && m2.isNorth())
			return true;
		if(m1.isEast() && m2.isWest())
			return true;
		if(m1.isWest() && m2.isEast())
			return true;
		return false;
	}

	static byte inversDirection(byte b){
		if(Move.isNormal(b)){
			if(Move.isNorth(b)){
				return MOVE_SOUTH|MOVE_NORMAL;
			}
			if(Move.isSouth(b)){
				return MOVE_NORTH|MOVE_NORMAL;
			}
			if(Move.isEast(b)){
				return MOVE_WEST|MOVE_NORMAL;
			}
			if(Move.isWest(b)){
				return MOVE_EAST|MOVE_NORMAL;
			}
		}else{
			if(Move.isNorth(b)){
				return MOVE_SOUTH|MOVE_PUSH;
			}
			if(Move.isSouth(b)){
				return MOVE_NORTH|MOVE_PUSH;
			}
			if(Move.isEast(b)){
				return MOVE_WEST|MOVE_PUSH;
			}
			if(Move.isWest(b)){
				return MOVE_EAST|MOVE_PUSH;
			}
		}
		U.pr("Error, inversDirection() is no direction!");
		System.exit(0);
		return MOVE_NORMAL;
	}

	static byte getMoveDirection(Move d, boolean isNormal){
		if(isNormal){
			if(d.isNorth())
				return MOVE_NORTH|MOVE_NORMAL;
			if(d.isSouth())
				return MOVE_SOUTH|MOVE_NORMAL;
			if(d.isEast())
				return MOVE_EAST|MOVE_NORMAL;
			if(d.isWest())
				return MOVE_WEST|MOVE_NORMAL;
		}else{
			if(d.isNorth())
				return MOVE_NORTH|MOVE_PUSH;
			if(d.isSouth())
				return MOVE_SOUTH|MOVE_PUSH;
			if(d.isEast())
				return MOVE_EAST|MOVE_PUSH;
			if(d.isWest())
				return MOVE_WEST|MOVE_PUSH;
		}
		U.pr("Error, getMoveDirectin() is no direction!");
		System.exit(0);
		return MOVE_NORMAL;
	}

	static Move getMove(int i, boolean isPush){
		if(!isPush){
			if(i==0)
				return new Move((byte)(MOVE_NORTH|MOVE_NORMAL));
			if(i==1)
				return new Move((byte)(MOVE_EAST|MOVE_NORMAL));
			if(i==2)
				return new Move((byte)(MOVE_SOUTH|MOVE_NORMAL));
			if(i==3)
				return new Move((byte)(MOVE_WEST|MOVE_NORMAL));
		}else{
			if(i==0)
				return new Move((byte)(MOVE_NORTH|MOVE_PUSH));
			if(i==1)
				return new Move((byte)(MOVE_EAST|MOVE_PUSH));
			if(i==2)
				return new Move((byte)(MOVE_SOUTH|MOVE_PUSH));
			if(i==3)
				return new Move((byte)(MOVE_WEST|MOVE_PUSH));
		}
		U.pr("Error, getMove() is no direction!");
		System.exit(0);
		return null;
	}

	// 0 ==> NORTH
	// 1 ==> EAST
	// 2 ==> SOUTH
	// 3 ==> WEST
	static int[] nextPos(int dir, int[] rc){
		if(dir==0)
			return new int[]{rc[0]-1, rc[1]};//NORTH
		if(dir==1)
			return new int[]{rc[0], rc[1]+1};//EAST
		if(dir==2)
			return new int[]{rc[0]+1, rc[1]};//SOUTH
		if(dir==3)
			return new int[]{rc[0], rc[1]-1};//WEST
		U.pr("Error, nextPos() is no direction!");
		System.exit(0);
		return null;
	}

	static void pr(Object msg){
		System.out.println(""+msg);
	}
}
